Satellite navigation systems are becoming increasingly important in a wide range of applications, including handheld devices for position determination, in-car navigation support, and so on. The main satellite navigation system in service at present is the global positioning system (GPS) operated by the United States Department of Defense. Worldwide sales of GPS equipment reached nearly 3.5 billion dollars by 2003, and this figure is expected to grow steadily over the next few years. A European counterpart satellite navigation system, named Galileo, is planned for launch and service availability later this decade.
A satellite navigation system comprises a constellation of satellites that each broadcasts one or more signals to earth. The basic components of a satellite signal are a spreading code (also referred to as a positioning, synchronisation or ranging code) which is combined with navigation data. The resulting combination is then modulated onto a carrier at a set frequency for transmission to earth. In some cases, multiple signals (referred to as channels) may be modulated onto a single carrier via some appropriate multiplexing scheme. In addition, each satellite generally transmits at multiple frequencies, which can help to compensate for any atmospheric distortion.
The spreading code component of a satellite signal typically comprises a predetermined sequence of bits (sometimes referred to as ‘chips’) and is used to perform two main tasks. Firstly, the spreading code provides a synchronisation mechanism to allow a receiver to lock onto a satellite signal. Thus each satellite (and typically each channel broadcast from that satellite) has its own synchronisation code. When a receiver is first switched on, it does not know which satellite signals can be received, since certain satellites in the constellation will be below the horizon for that particular location at that particular time. The receiver uses the synchronisation codes to lock into a signal from a first satellite. Once this has been done, the navigation data in the signal can be accessed. This then provides ephemeris data for the other satellites in the constellation, and allows the remaining satellites that are visible to the receiver to be acquired relatively quickly.
The second main task of a spreading code is to provide a distance estimate from the satellite to the receiver, based on the time that it has taken the signal to travel from the satellite to the receiver, which can be expressed as: c(Tr−Ts), where:
c is the velocity of light (known, subject to ionospheric effects, etc),
Ts is the time of sending from the satellite, which is encoded into the signal itself, and
Tr is the time of signal receipt at the receiver.
The position of the receiver can then be determined in three-dimensional space by using a process of trilateration, given the known positions of the satellites (as specified in their navigation data). In theory, this can be performed with signal information from a minimum of three satellites. In practice however we can write Tr=Tm+o, where Tm is the measured time of receipt at the receiver, and o is the offset between the receiver clock and satellite clock, which is generally unknown, except for specialised receivers. This then implies that signal information is obtained from at least one additional satellite to compensate for the unknown time offset at the receiver. If signals from further satellites are available, a statistical position determination can be performed using any appropriate algorithm such as least squares. This can also provide some indication of the error associated with an estimated position.
One important parameter for the spreading code is the bit rate at which the spreading code is transmitted, since this in turn controls the accuracy with which the positional determination can be made. For example, with a bit rate of 1 MHz, each bit represents a light travel time of 300 meters. The positioning accuracy is then determined by how accurately the phase offset between the satellite and the receiver can be judged for a single bit. This is generally dependent upon the noise in the system. For example, if the phase offset can be measured to an accuracy of 90 degrees (π/2), this corresponds to a positional determination of 75 meters. It will be appreciated that having a higher bit rate for the spreading code allows more accurate position determinations to be made.
Another important parameter for the spreading code is its total length, in other words the number of bits or chips in the spreading code before it repeats. One reason for this is that the finite length of the spreading code can lead to ambiguity in the position determination. For example, assume that the bit rate is 10 MHz and the total length of the bit sequence is 256 bits, which therefore corresponds to a light travel time of 7.68 km. The distance measurement from the satellite to the receiver is not uniquely specified, but rather can only be expressed as 7.68n+d km, where d is determined by the relative timing of the spreading code as broadcast and as received, but n is an unknown integer. There are various ways in which the ambiguity as to the value of n can be resolved, including using signals from a larger number of satellites, or by using knowledge of an approximate position derived from some other source. One common approach is to relate the code phase to the bit edge of the navigation data bit (this process is called bit synchronization), and also to relate the bit edge to the time of week (ToW) contained in the navigation data transmitted by the satellite.
It will be appreciated that increasing the repetition length for the spreading code helps to reduce problems with ambiguous distance determinations. A longer length for the spreading code also provides better separation of signals from different sources, and increased robustness against interference. On the other hand, having a longer repetition length for the spreading code may delay initial acquisition of the signal, as well as requiring more processing capability within the receiver. One known strategy to counter this problem is to use a hierarchical spreading code based on primary and secondary codes. If we assume that the primary code has N1 bits and the secondary code has N2 bits, then the first N1 bits of the overall spreading code correspond to the primary sequence exclusive-ORed with the first bit of the secondary code, the next N1 bits of the spreading code comprise a repeat of the N1 bits of the primary code, this time exclusive-ORed with the second bit of the secondary code, and so on. This gives a total repetition length for the code of N1×N2. However, the repetition length for synchronisation purposes is only N1, since the primary code will still give a correlation peak irrespective of the value of the bit from the secondary code (this will just change the sign of the correlation peak).
The GPS spreading codes are implemented using linear feedback shift registers (LFSRs), in which selected outputs from an N-stage shift register are tapped and fed back to the input. The feedback connections within the LFSR can be represented as a polynomial of order N, whereby the operation of an LFSR can be fully specified by its polynomial and the initial setting of the LFSR.
GPS uses a subset of LFSRs known as Gold codes that have certain special mathematical properties. One of these is that they generate an output of pseudo-random noise having a maximal repetition length of 2N−1, so that a relatively compact LFSR can generate an output with a long repetition length. Gold codes also have good auto-correlation properties that support accurate positioning. In particular, the autocorrelation function has a well-defined peak at zero time shift, and is relatively small for all other (i.e. non-zero) time shifts. It is also possible to select a set of Gold codes that have good cross-correlation properties, whereby the cross-correlation function between different codes is kept relatively small. This is important for signal acquisition, since it helps to prevent a synchronisation code from one satellite being accidentally mistaken for a synchronisation code from another satellite. A further important practical criterion for a spreading code is to have equal (or nearly equal) numbers of ones and zeros—this is referred to as balancing.
Additional information about satellite navigation systems, and in particular about GPS, can be found in: “Re-Tooling the Global Positioning System” by Per Enge, p 64-71, Scientific American, May 2004, and in “Global Positioning System: Signals, Measurements and Performance”, by Misra and Enge, Ganga-Jamuna Press, 2001, ISBN 0-9709544-0-9. Information about the proposed Galileo signals can be found in: “Status of Galileo Frequency and Signal Design” by Hein et al, September 2002, available from: http://europa.eu.int/comm/dgs/energy_transport/galileo/doc/galileo_stf_ion2002.pdf, see also “Galileo Frequency and Signal Design” by Issler et al, GPS World, June 2003, available from: http://www.gpsworld.com/gpsworld/article/articleDetail.jsp?id=61244.
Although the use of Gold codes is well-established for existing satellite navigation systems, there are some limitations associated with such codes. For example, they are only available with certain code lengths (not all values of N can be used for the LFSR polynomial). In general, the code length is determined by the ratio of the chip rate of the spreading code and the bit rate of the navigation data. If the code length is restricted to an available Gold code, then this implies a constraint on the chip rate and the bit rate, which might in turn impact other considerations, such as acquisition time and positioning accuracy. In some cases, the limitation on code length for Gold codes has been overcome by using truncated Gold codes, but this truncation has an adverse impact on the mathematical properties of the code set (in terms of the autocorrelation function, etc).
In addition, the cross-correlation properties of Gold codes are not generally optimised for the situation where the polarity of the code changes from one repetition of the code to the next, in accordance with the navigation data that is being transmitted. This latter problem is exacerbated where the bit rate of the navigation data is relatively high (as for Galileo), since this leads to a significant probability that a spreading code transmission has the opposite polarity from the immediately preceding transmission of the spreading code.